package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

public class MergeIntervals {

    /**
     * 合并数组中能合并的区间，一直到不能合并为止
     * 合并过的区间的做个标记，不重复合并
     * 合并区间分为2种情况，假设两个区间分别为区间A{a, b} 和 区间 B{x, y}
     * 1. A和B重合 => {min(a, x), max(b, y)}
     * 2. A和B不重合 => 不发生合并
     *
     * @param intervals 1 <= intervals.length <= 104
     *                  intervals[i].length == 2
     *                  0 <= starti <= endi <= 104
     */
    public int[][] merge(int[][] intervals) {
        boolean flag = true;
        int len = intervals.length, L = len;
        while (flag){
            flag = false;
            for (int i = 0; i < len; ++i){
                // 合并过的区间不重复合并
                if (intervals[i][0] == - 1){
                    continue;
                }
                for (int j = i + 1; j < len; j++){
                    // 合并过的区间不重复合并
                    if (intervals[j][0] == - 1){
                        continue;
                    }
                    // 判断两个区间是否重叠
                    if (intervals[j][0] <=  intervals[i][1] && intervals[j][1] >= intervals[i][0]){
                        intervals[i][0] = Math.min(intervals[i][0], intervals[j][0]);
                        intervals[i][1] = Math.max(intervals[i][1], intervals[j][1]);
                        // 合并过的区间的做个标记，避免重复合并
                        intervals[j][0] = -1;
                        flag = true;
                        L--;
                    }
                }
            }

        }
        int[][] res = new int[L][2];
        for (int i = 0, j = 0; i < len; ++i){
            if (intervals[i][0] != -1){
                res[j++] = intervals[i];
            }
        }
        return res;
    }



    public static void main(String[] args) {
        int[][] ints = ArrayUtils.parseArray("" +
                "[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]" +
                "", int[].class);
        int[][] merge = new MergeIntervals().merge(ints);
        PrintUtils.println(merge);
    }
}
